#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;


// 摆动序列
// https://leetcode.cn/problems/wiggle-subsequence/description/
//class Solution {
//public:
//    int wiggleMaxLength(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 1) return 1;
//
//        vector<int> f(n, 1), g(n, 1);
//        int ret = 0;
//        for (int i = 1; i < n; ++i)
//        {
//            for (int j = i; j >= 1; --j)
//            {
//                //上升趋势
//                if (nums[j] > nums[j - 1]) f[i] = max(f[i], g[j - 1] + 1);
//                else if (nums[j] < nums[j - 1]) g[i] = max(g[i], f[j - 1] + 1);
//                ret = max(f[i], g[i]);
//            }
//        }
//        //return max(f[n - 1], g[n - 1]);
//        return ret;
//    }
//};

// 最长递增子序列的个数
// https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/
// class Solution {
// public:
//     int findNumberOfLIS(vector<int>& nums) {
//         int n = nums.size();

//         //len表示在i位置下最长子序列长度
//         //count表示在i位置len长度下最长子序列个数
//         vector<int> len(n,1),count(n,1);
//         int maxlen = 1,ret = 1; //长度和数量一开始都是1
//         for(int i = 1;i<n;++i)
//         {
//             for(int j = 0;j<i;++j) //在[0,i-1]位置逐一判断是否有能构成子序列的值
//             {
//                 if(nums[i] > nums[j]) //如果可以构成子序列
//                 {
//                     // 1 2 2 3 例如其中2出现了两次 这两个2都可以到达3 所以当这两个2的长度都需要加在3上表示都可以构成以3结尾的子序列
//                     if(len[i] == len[j]+1) count[i] += count[j]; //表示在i位置下 如果长度相等 则该位置的最长子序列计数+j位置的最长子序列长度
//                     else if(len[i] < len[j]+1) //如果长度可以更长
//                     {
//                         len[i] = len[j]+1;
//                         count[i] = count[j];
//                     }
//                 }
//             }
//             if(maxlen == len[i]) ret += count[i]; //如果当前长度与最大长度相等 则加上当前长度的最长子序列数量
//             else if(maxlen < len[i]) maxlen = len[i],ret = count[i]; //如果比当前最大长度大 则更新最大长度和当前最新最大长度的子序列数量
//         }
//         return ret;
//     }
// };

// 最长数对链
// https://leetcode.cn/problems/maximum-length-of-pair-chain/description/
// class Solution {
// public:
//     int findLongestChain(vector<vector<int>>& pairs) {
//         int n = pairs.size();
//         sort(pairs.begin(),pairs.end());

//         vector<int> v(n,1); //最长数对链的最小长度为1
//         int ret = 1;
//         for(int i = 1;i<n;++i)
//         {
//             for(int j = 0;j<i;++j)
//                 if(pairs[j][1] < pairs[i][0]) v[i] = max(v[i],v[j]+1);
//             ret = max(v[i],ret);
//         }

//         return ret;
//     }
// };


